// hdu5072
// 题意：给定n(<=10^5)个数，每个数都不超过10^5，现在问这n个数中有多少三
//       元组(a, b, c)使得要么gcd(a, b) = gcd(b, c) = gcd(a, c) = 1或者
//       gcd(a, b) != 1 且 gcd(b, c) != 1 且 gcd(a, c) != 1 成立。
//
// 题解：题目翻一下就是求三元组要么两两都互素，要么两两都不互素。直接求
//       比较难求，我们可以求逆命题即三元组(a, b, c)，要么a, b互素a, c
//       不互素，要么就是a, b不互素，a, c互素。换过来说，对于一个数a，
//       我们要求这n个数中有多少个与它不互素的，记做t，那么
//         (t - 1) * (n - t) 就是这个值对逆命题三元组的贡献，对于所有数
//       都求一遍这个值然后加起来除以2就是逆命题的解，然后C(n, 3)减去她
//       就是原命题的解。要注意的是如果遇到的数是1直接跳过就行。
//      
// run: $exec < input
#include <iostream>
#include <cstring>
#include <vector>

int constexpr maxn = 100007;
int deg[maxn];
int count[maxn];
bool single[maxn];
std::vector<int> fact[maxn];
int a[maxn];
int n;

long long c3(long long x)
{
	return (x - 2) * (x - 1) * x / 6;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::memset(single, 1, sizeof(single));
	for (int i = 2; i < maxn; i++) {
		for (int j = i; j < maxn; j += i) fact[j].push_back(i);
		if (!single[i]) continue;
		if (!deg[i]) deg[i] = 1;
		for (int j = 1; i * j < maxn; j++)
			if (j > 1 && deg[i] == 1) {
				if (!(j % i)) single[i * j] = false;
				else deg[i * j]++;
			}
	}

	int T; std::cin >> T;
	while (T--) {
		std::memset(count, 0, sizeof(count));
		std::cin >> n;
		for (int i = 1; i <= n; i++) {
			std::cin >> a[i];
			for (int j = 0; j < (int)fact[a[i]].size(); j++)
				count[fact[a[i]][j]]++;
		}

		long long ans = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] == 1) continue;
			long long sum = 0;
			for (int j = 0; j < (int)fact[a[i]].size(); j++) {
				auto tmp = fact[a[i]][j];
				if (!single[tmp]) continue;
				if (deg[tmp] & 1) sum += count[tmp];
				else sum -= count[tmp];
			}
//			std::cout << "i = " << i << "  sum = " << sum << '\n';
			ans += (sum - 1) * (n - sum);
		}
		std::cout << c3(n)- ans / 2 << '\n';
	}
}

